#include <iostream>


using namespace std;

class LinkStack{
private:
    struct Node{
        int data;
        Node *next;
        Node():data(0),next(NULL){}
        Node(int val):data(val),next(NULL){}
        Node(int val, Node *next):data(val),next(next){}
    };
    Node *head_;
    int size_;

public:
    LinkStack()
    {
        head_ = new Node(-1);
        size_ = 0;
    }
    ~LinkStack()
    {
        Node *p = head_->next;
        while(p != NULL)
        {
            Node *q = p;
            p = p->next;
            delete q;
        }
    }
    void push(int val);
    int pop();
    int top() const;
    bool empty() const;
    int size() const;
};

bool LinkStack::empty() const
{
    return head_->next == NULL;
}

void LinkStack::push(int val)
{
    Node *p = new Node(val);
    p->next = head_->next;
    head_->next = p;
    size_++;
}

int LinkStack::pop()
{
    if (empty())
    {
        throw "stack is empty";
    }
    Node *p = head_->next;
    int val = p->data;
    head_->next = p->next;
    delete p;
    size_--;
    return val;
}

int LinkStack::size() const
{
    return size_;
}

int LinkStack::top() const
{
    if (empty())
    {
        throw "stack is empty";
    }
    return head_->next->data;
}



int main(int argc, const char** argv) {
    LinkStack s;
    int arr[] = {1,2,3,4,5,6,7,8,9,10};

    for (int val : arr)
    {
        s.push(val);
        cout << s.top() << endl;
    }

    int length = s.size();
    cout << "s.size() =: " << length << endl;

    while (s.empty() == false)
    {
        cout << s.pop() << endl;
    }

    return 0;
}